﻿//力扣：1419. 数青蛙
//https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/


//方法一：计数
// 时间复杂度：O(n)
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        // 若长度不是5的倍数，则一定无法组成完整的 "croak" 叫声
        if (croakOfFrogs.size() % 5 != 0) 
        {
            return -1;
        }

        int res = 0;                                // 结果：最小需要的青蛙数量
        int frogNum = 0;                            // 当前正在叫的青蛙数量
        vector<int> cnt(4);                         // 计数数组，用来记录 "c", "r", "o", "a" 阶段的数量
        unordered_map<char, int> mp = { {'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4} }; // 字符到阶段的映射

        // 遍历整个字符串
        for (char c : croakOfFrogs) 
        {
            int t = mp[c];                          // 将字符映射到阶段 0 到 4（依次对应 'c', 'r', 'o', 'a', 'k'）

            if (t == 0)                             // 当前字符为 'c' 表示一个新的 "croak" 开始
            {         
                cnt[t]++;                           // "c"阶段数量加1
                frogNum++;                          // 新增一个正在叫的青蛙

                if (frogNum > res) 
                {
                    res = frogNum;                  // 更新所需最小青蛙数
                }
            }
            else                                    // 若当前字符不是 "c" 则需保证前一个阶段有对应的字符数量
            {
                
                if (cnt[t - 1] == 0) 
                {
                    return -1;                      // 前一个阶段字符不足，说明顺序不对，返回 -1
                }

                cnt[t - 1]--;                       // 减少前一阶段字符数量

                if (t == 4)                         // 到达 "k" 表示一个 "croak" 结束
                {     
                    frogNum--;                      // 一个青蛙完成叫声，正在叫的青蛙数量减1
                }
                else 
                {
                    cnt[t]++;                       // 否则增加当前阶段字符数量
                }
            }
        }

        // 如果遍历完成后仍有未完成的叫声，返回 -1
        if (frogNum > 0) 
        {
            return -1;
        }

        return res;                                 // 返回最小需要的青蛙数量
    }
};
//叫声顺序管理：
// · 遍历字符串中的每个字符c。
// · 当字符为"c"时，意味着一个新青蛙叫声的开始，因此增加cnt[0]和frogNum（当前在叫的青蛙数），并更新res（最小青蛙数）。
// · 如果字符不是"c"，则必须检查它是否符合顺序要求：即前一阶段字符数量必须大于0，否则返回 - 1。
// · 对于字符"k"，表示当前青蛙叫声完成，因此减少frogNum。






//方法二：模拟 + 分情况讨论 + 哈希表
// 时间复杂度：O(n)
//算法原理：
//模拟⻘蛙的叫声。
//◦ 当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有⻘蛙叫出来。
//    如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有，直接返回 - 1 ；
//◦ 当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有⻘蛙叫出来。
//    如果有，就让这个⻘蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞⼀个⻘蛙。
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string t = "croak";                     // 目标青蛙叫声顺序
        int n = t.size();
        vector<int> hash(n);                    // 使用一个数组来模拟哈希表，记录每个阶段的字符数量

        unordered_map<char, int> index;         // 映射字符到索引： 'c' -> 0, 'r' -> 1, etc.
        for (int i = 0; i < n; i++)
        {
            index[t[i]] = i;                    // 初始化index表，将每个字符对应的下标存入其中
        }

        // 遍历输入字符串 `croakOfFrogs`，模拟青蛙的叫声顺序
        for (auto ch : croakOfFrogs) 
        {
            if (ch == 'c')                      // 当字符是 'c' (一声青蛙开始)
            {                 
                if (hash[n - 1] != 0)           // 若上一个完整的青蛙叫声还在结尾，则将其结束
                {
                    hash[n - 1]--;
                }

                hash[0]++;                      // 增加开始阶段 'c' 的数量
            }
            else                                // 若字符是'r', 'o', 'a', 或 'k'
            {                        
                int i = index[ch];              // 获取当前字符的顺序位置
                if (hash[i - 1] == 0)           // 若前一个字符不足，则表示顺序错误，返回 -1
                {
                    return -1;
                }

                hash[i - 1]--;                  // 减少前一个阶段的字符数量
                hash[i]++;                      // 增加当前阶段的字符数量
            }
        }

        // 检查是否所有的青蛙叫声都完整结束
        for (int i = 0; i < n - 1; i++)
        {
            if (hash[i] != 0)                   // 若某一阶段数量不为零，返回 -1
            {                
                return -1;
            }
        }

        return hash[n - 1];                     // 返回最后阶段的数量，即最小青蛙数
    }
};
//关键点解释:
//1. 哈希映射字符位置：字符串"croak"中的每个字符（c, r, o, a, k）被映射到相应的顺序索引（0到4），以便按叫声顺序检查每个字符是否在正确位置。
//
//2. 阶段记录数组 hash：
//hash[i] 表示有多少个青蛙正处于"croak"中第i个字符的阶段。
//当遍历到一个字符时，代码会更新其在“叫声阶段”中的位置。例如遇到'c'时，
//表示开始了一个新的青蛙叫声，hash[0]加1；遇到'k'时，表示完成一个完整的叫声，hash[n - 1]减1。
//
//3. 字符验证与阶段推进：
//若当前字符是c，说明是一个新的叫声开始。如果之前的hash[n - 1]大于0，表示前一个叫声已结束，所以减1并启动新叫声。
//对于'r', o, a, 和k字符，必须确保其前一个阶段的字符数量足够（顺序完整性检查），否则直接返回 - 1（说明字符顺序不匹配）。
//
//4. 最终检查：
//循环结束后，所有的叫声阶段（c, r, o, a）的字符数量必须为0（即所有叫声完整结束），否则返回 - 1。